package com.lanyun.common;

import com.lanyun.util.Address;
import lombok.Data;

import java.util.Random;

/**
 * 遗传算法实现类
 *
 * @author: Li Ning Ning
 * @time: 2021/7/31 10:46
 * @description: TODO
 * @version: 1.0
 */
@Data
public class GA {

    /**
     * 种群规模
     */
    private int scale;

    /**
     * 城市数量，染色体长度
     */
    private int cityNum;

    /**
     * 迭代次数
     */
    private int iterMax;

    /**
     * 交叉概率
     */
    private double crossoverProbability;

    /**
     * 变异概率
     */
    private double mutationProbability;

    /**
     * 距离矩阵
     */
    private int[][] distance;

    /**
     * 最佳路径
     */
    private int[] bestRoute;

    /**
     * 最佳长度
     */
    private int bestRouteLength;

    /**
     * 初始种群，父代种群，行数表示种群规模，一行代表一个个体，即染色体，列表示染色体基因片段
     */
    private int[][] oldPopulation;

    /**
     * 新的种群，子代种群
     */
    private int[][] newPopulation;

    /**
     * 种群适应度，表示种群中各个个体的适应度
     */
    private int[] fitness;

    /**
     * 种群中各个个体的累计概率
     */
    private double[] cumulativeProbability;

    /**
     * 最佳路径地址
     */
    private String[] address;

    /**
     * 城市坐标x
     */
    private int[] x;

    /**
     * 城市坐标y
     */
    private int[] y;

    private Random random;

    public GA() {

    }

    public GA(int scale, int iterMax, double crossoverProbability, double mutationProbability) {
        this.scale = scale;
        this.iterMax = iterMax;
        this.crossoverProbability = crossoverProbability;
        this.mutationProbability = mutationProbability;
    }

    public GA(int cityNum, int scale, int iterMax, double crossoverProbability, double mutationProbability) {
        this.cityNum = cityNum;
        this.scale = scale;
        this.iterMax = iterMax;
        this.crossoverProbability = crossoverProbability;
        this.mutationProbability = mutationProbability;
    }

    /**
     * 初始化参数
     *
     * @param distance 距离矩阵
     * @param address  位置数组
     */
    public GA init(int[][] distance, String[] address) {
        //初始化距离矩阵
        this.distance = distance;
        //初始化地址
        this.address = address;
        //初始化参数
        initParams();
        return this;
    }


    /**
     * 初始化参数
     */
    private void initParams() {
        //初始化路径
        bestRoute = new int[cityNum + 1];
        //初始化路径长度
        bestRouteLength = Integer.MAX_VALUE;
        //初始化种群
        newPopulation = new int[scale][cityNum];
        oldPopulation = new int[scale][cityNum];
        //初始化种群适应度
        fitness = new int[scale];
        //初始化种群个体累计概率
        cumulativeProbability = new double[scale];
        //初始化随机变量
        random = new Random(System.currentTimeMillis());
    }

    /**
     * 多次迭代路径
     *
     * @return 路径列表
     */
    public Long[] solve() {
        //初始化种群
        initGroup();
        //计算初始化种群适应度
        for (int i = 0; i < scale; i++) {
            fitness[i] = evaluate(oldPopulation[i]);
        }
        // 计算初始化种群中各个个体的累积概率
        computeCumulativeProbability();
        for (int t = 0; t < iterMax; t++) {
            evolution();
            // 将新种群newGroup复制到旧种群oldGroup中，准备下一代进化
            for (int i = 0; i < scale; i++) {
                if (cityNum >= 0) {
                    System.arraycopy(newPopulation[i], 0, oldPopulation[i], 0, cityNum);
                }
            }
            // 计算种群适应度
            for (int i = 0; i < scale; i++) {
                fitness[i] = evaluate(oldPopulation[i]);
            }
            // 计算种群中各个个体的累积概率
            computeCumulativeProbability();
        }
        Long[] routes = formatData();
        printOptimal();
        return routes;
    }

    /**
     * 初始化种群
     */
    private void initGroup() {
        int i, j, k;
        // 获取个体
        for (i = 0; i < scale; i++) {
            oldPopulation[i][0] = random.nextInt(65535) % cityNum;
            // 获取染色体
            for (j = 1; j < cityNum; ) {
                oldPopulation[i][j] = random.nextInt(65535) % cityNum;
                // 染色体不能相同
                for (k = 0; k < j; k++) {
                    if (oldPopulation[i][j] == oldPopulation[i][k]) {
                        break;
                    }
                }
                if (k == j) {
                    j++;
                }
            }
        }
    }

    private int evaluate(int[] chromosome) {
        int len = 0;
        // 染色体，起始城市,城市1,城市2...城市n
        for (int i = 1; i < cityNum; i++) {
            len += distance[chromosome[i - 1]][chromosome[i]];
        }
        len += distance[chromosome[cityNum - 1]][chromosome[0]];
        return len;
    }

    /**
     * 计算种群中各个个体的累积概率，作为赌轮选择策略一部分
     */
    private void computeCumulativeProbability() {
        int k;
        double sumFitness = 0;// 适应度总和
        double[] temp = new double[scale];

        for (k = 0; k < scale; k++) {
            temp[k] = 10.0 / fitness[k];
            sumFitness += temp[k];
        }
        // 第0个不用加
        cumulativeProbability[0] = temp[0] / sumFitness;
        for (k = 1; k < scale; k++) {
            // 各个个体的概率加在一起就是累积概率
            cumulativeProbability[k] = temp[k] / sumFitness + cumulativeProbability[k - 1];
        }
    }

    /**
     * 进化函数，保留最好染色体不进行交叉变异
     */
    private void evolution() {
        int i;
        // 挑选种群中适应度最高的个体
        selectBestIndividual();
        // 赌轮选择策略挑选scale-1个下一代个体
        selectIndividual();
        // 概率
        double probability;
        for (i = 1; i + 1 < scale / 2; i = i + 2) {
            probability = random.nextDouble();
            if (probability < crossoverProbability) {
                // 交叉
                OXCross(i, i + 1);
            } else {
                probability = random.nextDouble();
                // 变异
                if (probability < mutationProbability) {
                    // 多次随机交换2个基因
                    mutation(i);
                }
                probability = random.nextDouble();
                // 变异
                if (probability < mutationProbability) {
                    // 多次随机交换2个基因
                    mutation(i + 1);
                }
            }
        }
        if (i == scale / 2 - 1) {// 剩最后一个染色体没有交叉
            probability = random.nextDouble();// /产生概率
            if (probability < mutationProbability) {
                mutation(i);
            }
        }
    }

    /**
     * 挑选种群中适应度最高的个体，直接复制到子代中
     */
    private void selectBestIndividual() {
        int bestId = 0;
        int bestEvaluation = fitness[0];
        for (int i = 1; i < scale; i++) {
            if (bestEvaluation > fitness[i]) {
                bestEvaluation = fitness[i];
                bestId = i;
            }
        }
        if (bestRouteLength > bestEvaluation) {
            bestRouteLength = bestEvaluation;
            System.arraycopy(oldPopulation[bestId], 0, bestRoute, 0, cityNum);
        }
        // 复制染色体，k表示新染色体在种群中的位置，kk表示旧的染色体在种群中的位置
        copyChromosome(0, bestId);
    }

    /**
     * 赌轮选择策略挑选
     */
    private void selectIndividual() {
        int j, selectId;
        for (int i = 1; i < scale; i++) {
            double random1 = random.nextInt(65535) % 1000 / 1000.0;
            for (j = 0; j < scale; j++) {
                if (random1 <= cumulativeProbability[j]) {
                    break;
                }
            }
            selectId = j;
            copyChromosome(i, selectId);
        }
    }

    /**
     * 复制染色体，k表示新染色体在种群中的位置，kk表示旧的染色体在种群中的位置
     *
     * @param dest 目的数组
     * @param src  源数组
     */
    private void copyChromosome(int dest, int src) {
        System.arraycopy(oldPopulation[src], 0, newPopulation[dest], 0, cityNum);
    }

    /**
     * OX交叉算子
     *
     * @param k1 第一个个体
     * @param k2 第二个个体
     */
    private void OXCross(int k1, int k2) {
        int i, j, k;
        int[] individual1 = new int[cityNum];
        int[] individual2 = new int[cityNum];
        int random1 = random.nextInt(65535) % cityNum;
        int random2 = random.nextInt(65535) % cityNum;
        while (random1 == random2) {
            random2 = random.nextInt(65535) % cityNum;
        }

        //确保random1<random2
        if (random1 > random2) {
            int temp = random1;
            random1 = random2;
            random2 = temp;
        }

        //生成子代，并保证子代中被选中的基因的位置与父代相同
        int flag = random2 - random1 + 1;
        for (i = 0, j = random1; i < flag; i++, j++) {
            individual1[i] = newPopulation[k2][j];
            individual2[i] = newPopulation[k1][j];
        }

        //找出第一步选中的基因在另一个父代中的位置，再将其余基因按顺序放入上一步生成的子代中
        for (i = 0, j = flag; j < cityNum; ) {
            individual1[j] = newPopulation[k1][i++];
            for (k = 0; k < flag; k++) {
                if (individual1[k] == individual1[j]) {
                    break;
                }
            }
            if (k == flag) {
                j++;
            }
        }
        for (i = 0, j = flag; j < cityNum; ) {
            individual2[j] = newPopulation[k2][i++];
            for (k = 0; k < flag; k++) {
                if (individual2[k] == individual2[j]) {
                    break;
                }
            }
            if (k == flag) {
                j++;
            }
        }

        //交叉完毕放回种群
        for (i = 0; i < cityNum; i++) {
            newPopulation[k1][i] = individual1[i];
            newPopulation[k2][i] = individual2[i];
        }
    }

    /**
     * 变异算子
     *
     * @param k
     */
    private void mutation(int k) {
        int count = random.nextInt(65535) % cityNum;
        //多次随机交换2个基因
        for (int i = 0; i < count; i++) {
            int random1 = random.nextInt(65535) % cityNum;
            int random2 = random.nextInt(65535) % cityNum;
            while (random1 == random2) {
                random2 = random.nextInt(65535) % cityNum;
            }
            //交换基因
            int temp = newPopulation[k][random1];
            newPopulation[k][random1] = newPopulation[k][random2];
            newPopulation[k][random2] = temp;
        }
    }


    private Long[] formatData() {
        // 将数组排序成从第一个城市开始
        bestRoute = Address.StartAtZero(bestRoute);
        // 将染色体编号转为为对应的景点ID
        address = Address.arrayToAddress(bestRoute, address);
        Long[] ids = new Long[bestRoute.length];
        for (int i = 0; i <bestRoute.length; i++) {
            ids[i] = Long.valueOf(address[i]);
        }
        return ids;
    }
    //        ArrayList<Route> routes = new ArrayList<>();
//        for (int i = 0; i < bestRoute.length; i++) {
//            Route route = new Route();
//            route.setNumber(bestRoute[i]);
//            route.setAddress(address[i]);
//            route.setDistance(distance[bestRoute[i]][bestRoute[(i + 1) % bestRoute.length]]);
//            route.setTotalCity(address.length - 1);
//            route.setTotalDistance(bestRouteLength);
//            if (x != null && y != null) {
//                route.setNode(new Node(x[bestRoute[i]], y[bestRoute[i]]));
//            }
//            routes.add(route);
//        }
    private void printOptimal() {
        System.out.println("遗传算法: ");
        System.out.println("The optimal length is: " + bestRouteLength);
        System.out.println("The optimal tour is: ");
        for (int i = 0; i < cityNum + 1; i++) {
            System.out.print(bestRoute[i] + " ");
        }
        System.out.println();
    }
}
